package com.jlhlyby.other;

import java.util.ArrayList;
import java.util.HashMap;

/**
 * 牛客网：实现lru算法
 */
public class Solution {
    public static void main(String[] args) {

        Solution s = new Solution();
        int[][] arr = {{1,1,1}, {1,2,2}, {1,3,2}, {2,1,0},{1,4,4},{2,2,0}};
        s.LRU(arr,3);
    }
    /**
     * lru design
     * @param operators int整型二维数组 the ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    public int[] LRU (int[][] operators, int k){
        ArrayList<Integer> res = new ArrayList();
        LRUCash lruCash = new LRUCash(k);
        for(int i = 0; i<operators.length;i++){
            if(operators[i][0] == 1){
                lruCash.set(operators[i][1],operators[i][2]);
            }else if(operators[i][0] == 2){
                res.add(lruCash.get(operators[i][1]));
            }
        }
        int [] resArrary = new int[res.size()];
        for (int i = 0; i < res.size(); i++){
            resArrary[i] = res.get(i);
        }

        return resArrary;
    }
    public class LRUCash{
        private HashMap<Integer,Node> map = new HashMap();
        private Node head = new Node(-1,-1);
        private Node tail = new Node(-1,-1);
        private int size;
        private int max;
        public LRUCash(int max){
            this.max = max;
            head.next = tail;
            tail.pre = head;
        }
        public void set(int key,int val){
            if(map.containsKey(key)){
                Node node = map.get(key);
                node.value = val;
            }else{
                Node node = new Node(key,val);
                map.put(key,node);
                if(size >= max){
                    removeNode();
                }
                addToHead(node);
                size++;
            }

        }
        public int get(int key){
            Node node = map.get(key);
            if(node == null){
                return -1;
            }
            moveToHead(node);
            return node.value;
        }
        private void removeNode(){
            if(tail.pre != head){
                Node node  = tail.pre;
                map.remove(node.key);
                node.pre.next = node.next;
                node.next.pre = node.pre;
                size--;
            }
        }
        private void moveToHead(Node node){
            if(node == null){
                return;
            }
            node.pre.next = node.next;
            node.next.pre = node.pre;
            addToHead(node);
        }
        private void addToHead(Node node){
            node.pre = head;
            node.next = head.next;
            head.next.pre = node;
            head.next = node;

        }


    }
    public class Node{
        public int key;
        public int value;
        public Node next;
        public Node pre;
        public Node(int key,int value){
            this.value = value;
            this.key = key;
        }
    }
}